package company.bytedance.string

import kotlinetc.println


/**
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例1:

输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").


示例2:

输入: s1= "ab" s2 = "eidboaoo"
输出: False


注意：

输入的字符串只包含小写字母
两个字符串的长度都在 [1, 10,000] 之间
 */

fun main(args: Array<String>) {

    checkInclusion("adc", "dcda").println()
}

fun checkInclusion(s1: String, s2: String): Boolean {

    val table = Array(26, { 0 })
    val sTable = Array(26, { 0 })
    s1.forEach {
        val i = it.toInt() - 'a'.toInt()
        table[i]++
    }

    var count = 0

    s2.forEachIndexed { index, it ->

        val i = it.toInt() - 'a'.toInt()
        if (table[i] != 0) {
            count++
            sTable[i]++
        } else {

            count = 0
            resetTable(sTable)
        }

        if (s2.lastIndex - index < s1.length - count)//剩余字符串 少于 需要的字符数
            return false


        //已经读取到了 目标字符串的长度，进行检测
        if (count == s1.length)
            if (checkSatisfied(table, sTable))
                return true
            else count = 0

    }


    return false
}

fun resetTable(sTable: Array<Int>) {
    var i = 0
    while (i < sTable.size) {
        sTable[i] = 0
        i++
    }
}

fun checkSatisfied(t: Array<Int>, s: Array<Int>): Boolean {

    t.forEachIndexed { i, v ->
        if (v != 0 && v != s[i])
            return false
        else s[i] = 0  //比较过之后重置为 0，因为 如果比较不成功，说明遇到 不同字符，需要重置计数后重新计数
    }

    return true
}